For a network that guarantees quality of service (QoS) to individual connections, route determination is both a crucial component and a challenging problem. In such a network (e.g. an Asynchronous Transfer Mode, or ATM, network), data packets or cells belonging to a given connection follow a pre-established route across the network. For each connection, the chosen route is determined in such a way that the connection is guaranteed to receive the negotiated quality of service from each switching device along the route for the duration of the connection's existence.
The state-of-the-art QoS routing protocol currently available in the networking industry is a protocol developed by the ATM Forum called Private Network-Network Interface or PNNI [The ATM Forum, ATM Private Network-Network Interface Specification v. 1.0, April 1996, incorporated by reference herein]. PNNI routing protocol specifies what and how QoS information is exchanged among switching devices in the network. Each switching device originating a connection determines a route based on this information. Generally, computing a route satisfying a given set of QoS requirements boils down to a constrained optimization problem, which cannot be solved exactly in real time. The ATM Forum recognized this and left route determination unspecified in the PNNI specification, giving vendors freedom to experiment with and implement their own algorithms without breaking the protocol.
In a connection-oriented network such as ATM, connection setup rate is a very important performance parameter. The ability of such a network to support layer-3 protocols (such as Internet Protocol or IP) over it efficiently is very much dependent on being able to deliver sufficiently high connection setup rates. Route determination time constitutes a relatively large portion of connection setup latency, and therefore needs to be kept as small as possible.
PNNI is likely to become one of the most widely deployed routing protocols supporting QoS in the networking industry. Because route determination is not standardized, it represents one of the key differentiators among different networking vendors' PNNI implementations.
The present invention solves the QoS route determination problem by combining these two elements 1) approximate/heuristic (as opposed to exact) solutions to the constrained optimization problem and 2) route precomputation based on connection profiles. The contribution of the invention is in identifying what parameters are relevant in defining a profile and what information needs to be pre-computed to support the approximate solution, and in combining all the elements into an implementable algorithm.